#pragma once

#include "HaarCoeffCubemap.hpp"
namespace zzz{
template < int CUBEFACEN,class T1=float,typename T2=unsigned short > class HaarCoeffCubemap4TripleFull;

struct _s
{
  short l; //:8;  //256
  short i; //:12; //4096
  short j; //:12; //4096
};
enum _m{M01,M10,M11};
//////////////////////////////////////////////////////////////////////////
#define _SPARSENEW
template < int CUBEFACEN,class T1=float,typename T2=unsigned short >
class HaarCoeffCubemap4TripleSparse
{
public:
  typedef T1 VALUE_TYPE;
  typedef T2 INDEX_TYPE;
  VALUE_TYPE Scale[6];
  struct _coeff
  {
    Vector<3,VALUE_TYPE> value;
    INDEX_TYPE index;
    bool operator<(const _coeff &c)const {return index<c.index;}
  }*Coeff;
  int Size;
  const int LEVELN;
  static const int FACEDATASIZE=(CUBEFACEN*CUBEFACEN-1)/3;
  static const int DATASIZE=FACEDATASIZE*6;
  VALUE_TYPE EMPTYPSUM;
#ifdef SPARSENEW
  INDEX_TYPE IndexToLocal[DATASIZE];
#endif
  VALUE_TYPE *psum;
  bool psumanege_;
  const Vector<3,VALUE_TYPE> zerovalue;
  
  HaarCoeffCubemap4TripleSparse()
    :zerovalue(0),LEVELN(Log2(CUBEFACEN)),psumanege_(false)
  {
    Size=0;
    memset(Scale,0,sizeof(VALUE_TYPE)*6);
    memset(&EMPTYPSUM,1,sizeof(T1));
#ifdef SPARSENEW
    memset(IndexToLocal,0,sizeof(INDEX_TYPE)*DATASIZE);
#endif 
    Coeff=NULL;
    psum=NULL;
    psumanege_=false;
  }
  ~HaarCoeffCubemap4TripleSparse()
  {
    delete[] Coeff;
    if (psumanege_)
      delete[] psum;
  }
  inline void operator*=(const VALUE_TYPE &x)
  {
    for (int i=0; i<Size; i++)
      Coeff[i].value*=x;
    for (int i=0; i<6; i++)
      Scale[i]*=x;
  }
  inline void operator+=(const HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &h)
  {
    for(int i=0; i<6; i++)
      Scale[i]+=h.Scale[i];
#ifdef SPARSENEW
    _coeff *newdata=new _coeff[Size+h.Size];
    memcpy(newdata,Coeff,sizeof(_coeff)*Size);
    memcpy(newdata+Size,h.Coeff,sizeof(_coeff)*h.Size);
    delete[] Coeff;
    Coeff=newdata;
    Size+=h.Size;
    memset(IndexToLocal,0,sizeof(INDEX_TYPE)*DATASIZE);
    for (int i=0; i<Size; i++)
    {
      int index=Coeff[i].index;
      if (IndexToLocal[index]==0) IndexToLocal[index]=i;
      else
      {
        Coeff[IndexToLocal[i]].value+=Coeff[i].value;
        Coeff[i].value.v[0]=EMPTYPSUM;
      }
    }
#else
    _coeff* tmp=new _coeff[Size+h.Size];
    memset(tmp,0,sizeof(_coeff)*(Size+h.Size));
    _coeff *c1=Coeff,*c2=h.Coeff,*c1end=Coeff+Size,*c2end=h.Coeff+h.Size;
    if (c1==NULL)
    {
      *this=h;
      return;
    }
    int cur=0;
    while(c1!=c1end && c2!=c2end)
    {
      if (c1->value==0){c1++;continue;}
      if (c2->value==0){c2++;continue;}
      if (c1->index<c2->index)
      {
        tmp[cur]=(*c1);
        cur++;
        c1++;
      }
      else if (c1->index>c2->index)
      {
        tmp[cur]=(*c2);
        cur++;
        c2++;
      }
      else
      {
        tmp[cur].index=c1->index; ;
        tmp[cur].value=c1->value+c2->value;
        cur++;
        c1++;
        c2++;
      }
    }
    while (c1!=c1end)
    {
      if (c1->value==0){c1++;continue;}
      tmp[cur]=(*c1);
      cur++;
      c1++;
    }
    while (c2!=c2end)
    {
      if (c2->value==0){c2++;continue;}
      tmp[cur]=(*c2);
      cur++;
      c2++;
    }
    Size=cur;
    delete[] Coeff;
    Coeff=tmp;
#endif
  }
  inline void operator=(const HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &h)
  {
    memcpy(Scale,h.Scale,sizeof(VALUE_TYPE)*6);
    if (Size!=h.Size)
    {
      delete[] Coeff;
      Size=h.Size;
      if (Size!=0)
      {
        Coeff=new _coeff[Size];
        memcpy(Coeff,h.Coeff,sizeof(_coeff)*Size);
      }
      else Coeff=NULL;
    }
    else
      memcpy(Coeff,h.Coeff,sizeof(_coeff)*Size);
    PrepareIndexToLocal();
    if (psum!=NULL)
      memset(psum,1,sizeof(VALUE_TYPE)*DATASIZE);
  }

  const Vector<3,VALUE_TYPE> & operator[](INDEX_TYPE n) const
  {
    if (Coeff==NULL)
      return zerovalue;
    _coeff c;
    c.index=n;
    const _coeff *pos=lower_bound(Coeff,Coeff+Size,c);
    if (pos->index==n) return pos->value;
    else return zerovalue;
  }
  const Vector<3,VALUE_TYPE> *Find(INDEX_TYPE n)
  {
    if (Coeff==NULL)
      return NULL;
#ifdef SPARSENEW
    int pos=IndexToLocal[n];
    if (pos==0) return NULL;
    else return &(Coeff[pos].value);
#else
    _coeff c;
    c.index=n;
    const _coeff *pos=lower_bound(Coeff,Coeff+Size,c);
    if (pos->index==n) return &(pos->value);
    else return NULL;
#endif
  }
  inline void PrepareIndexToLocal()
  {
#ifdef SPARSENEW
    memset(IndexToLocal,0,sizeof(INDEX_TYPE)*DATASIZE);
    for(int i=0; i<Size; i++)
      IndexToLocal[Coeff[i].index]=i;
#endif
  }
  inline void Clear()
  {
    delete[] Coeff;
    Coeff=NULL;
    Size=0;
    memset(Scale,0,sizeof(VALUE_TYPE)*6);
    if (psum!=NULL)
      memset(psum,1,sizeof(VALUE_TYPE)*DATASIZE);
  }
  inline void Zero()
  {
    Clear();
  }
  inline void ResetPsum()
  {
    if (psum!=NULL)
      memset(psum,1,sizeof(VALUE_TYPE)*DATASIZE);
  }
  inline void Create(int n)
  {
    if (n==Size) return;
    Clear();
    Coeff=new _coeff[n];
    memset(Coeff,0,sizeof(_coeff)*n);
    Size=n;
  }
  VALUE_TYPE Dot(const HaarCoeffCubemap4TripleSparse<CUBEFACEN,T1,T2> &c)const
  {
    VALUE_TYPE ret=Scale[0]*c.Scale[0]+Scale[1]*c.Scale[1]+Scale[2]*c.Scale[2]+Scale[3]*c.Scale[3]+Scale[4]*c.Scale[4]+Scale[5]*c.Scale[5];
    if (c.Size==0) return ret;
    _coeff *cur1=Coeff,*cur2=c.Coeff,*end1=cur1+Size,*end2=cur2+c.Size;
    for (;cur1!=end1;cur1++)
    {
#ifdef SPARSENEW
      if (cur1->value.v[0]=EMPTYPSUM) continue;
      int index=cur1->index;
      int pos2=c.IndexToLocal[index];
      if (pos2==0) continue;
      ret+=cur1->value.Dot(c.Coeff[pos2].value);
#else
      while(cur2!=end2 && cur1->index > cur2->index) cur2++;
      if (cur2==end2) break;
      if (cur1->index==cur2->index)
        ret+=cur1->value.Dot(cur2->value);
#endif
    }
    return ret;
  }
  VALUE_TYPE Dot(const HaarCoeffCubemap4TripleFull<CUBEFACEN,T1,T2> &c)const
  {
    VALUE_TYPE ret=Scale[0]*c.Scale[0]+Scale[1]*c.Scale[1]+Scale[2]*c.Scale[2]+Scale[3]*c.Scale[3]+Scale[4]*c.Scale[4]+Scale[5]*c.Scale[5];
    for (int cur1=0;cur1<Size;cur1++)
    {
      ret+=Coeff[cur1].value.Dot(c.Square[Coeff[cur1].index]);
    }
    return ret;
  }
  void SaveToCubemap(Cubemap<VALUE_TYPE> &c)
  {
    const HaarCoeffCubemap4TripleFull<CUBEFACEN,INDEX_TYPE,INDEX_TYPE> &indextable=HaarCoeffCubemap4TripleFull<CUBEFACEN>::GetCubemapIndexTable();
    c.Zero();
    c.ChangeSize(CUBEFACEN);
    for(int sideIdx = 0; sideIdx < 6; ++sideIdx)
    {
      c.v[indextable.Scale[sideIdx]]=Scale[sideIdx];
    }
    for (int i=0; i<Size; i++)
    {
      c.v[indextable.Square[Coeff[i].index].v[0]]=Coeff[i].value.v[0];
      c.v[indextable.Square[Coeff[i].index].v[1]]=Coeff[i].value.v[1];
      c.v[indextable.Square[Coeff[i].index].v[2]]=Coeff[i].value.v[2];
    }
  }
  friend ostream& operator<<(ostream &o, HaarCoeffCubemap4TripleSparse<CUBEFACEN,T1,T2> &me)
  {
    me.SaveToFileA(o);
    return o;
  }
  friend istream& operator>>(istream &i, HaarCoeffCubemap4TripleSparse<CUBEFACEN,T1,T2> &me)
  {
    me.LoadFromFileA(i);
    return i;
  }
  void SaveToFileA(ostream &fo)
  {
    fo<<Scale[0]<<' '<<Scale[1]<<' '<<Scale[2]<<' '<<Scale[3]<<' '<<Scale[4]<<' '<<Scale[5]<<endl;
    fo<<Size<<endl;
    for(int i=0; i<Size; i++)
    {
      fo<<Coeff[i].value<<' ';
      fo<<Coeff[i].index<<' ';
    }
    fo<<endl;
  }
  void LoadFromFileA(istream &fi)
  {
    Clear();
    fi>>Scale[0]>>Scale[1]>>Scale[2]>>Scale[3]>>Scale[4]>>Scale[5];
    fi>>Size;
    Coeff=new _coeff[Size];
    for(int i=0; i<Size; i++)
    {
      fi>>Coeff[i].value;
      fi>>Coeff[i].index;
    }
    PrepareIndexToLocal();
  }
  void LoadFromFileA(FILE *fp)
  {
    printf("LoadFromFileA(FILE *fp) must be specilized to use!\n");
  }
  void SaveToFileB(FILE *fp)
  {
    fwrite(Scale,sizeof(VALUE_TYPE),6,fp);
    fwrite(&Size,sizeof(Size),1,fp);
    fwrite(Coeff,sizeof(_coeff),Size,fp);
  }
  void LoadFromFileB(FILE *fp)
  {
    Clear();
    fread(Scale,sizeof(VALUE_TYPE),6,fp);
    fread(&Size,sizeof(Size),1,fp);
    Coeff=new _coeff[Size];
    fread(Coeff,sizeof(_coeff),Size,fp);
    PrepareIndexToLocal();
  }
};

void HaarCoeffCubemap4TripleSparse<32,float,unsigned short>::LoadFromFileA(FILE *fp)
{
  Clear();
  fscanf(fp,"%f %f %f %f %f %f",Scale,Scale+1,Scale+2,Scale+3,Scale+4,Scale+5);
  fscanf(fp,"%d",&Size);
  Coeff=new _coeff[Size];
  for(int i=0; i<Size; i++)
  {
    fscanf(fp,"%f %f %f",&(Coeff[i].value[0]),&(Coeff[i].value[1]),&(Coeff[i].value[2]));
    fscanf(fp,"%hd",&(Coeff[i].index));
  }
}

//////////////////////////////////////////////////////////////////////////
template < int CUBEFACEN, int KEEPNUM, class T1=float,typename T2=unsigned short >
class HaarCoeffCubemap4TripleSparseStatic
{
public:
  typedef T1 VALUE_TYPE;
  typedef T2 INDEX_TYPE;
  VALUE_TYPE Scale[6];
  struct _coeff
  {
    Vector<3,VALUE_TYPE> value;
    INDEX_TYPE index;
    bool operator<(const _coeff &c)const {return index<c.index;}
  }Coeff[KEEPNUM];
  static const int Size=KEEPNUM;
  const int LEVELN;
  static const int FACEDATASIZE=(CUBEFACEN*CUBEFACEN-1)/3;
  static const int DATASIZE=FACEDATASIZE*6;
  T1 EMPTYPSUM;
  VALUE_TYPE *psum;
  bool psumanege_;
  const Vector<3,VALUE_TYPE> zerovalue;

  HaarCoeffCubemap4TripleSparseStatic()
    :zerovalue(0),LEVELN(Log2(CUBEFACEN)),psumanege_(false)
  {
    memset(Scale,0,sizeof(VALUE_TYPE)*6);
    memset(&EMPTYPSUM,1,sizeof(T1));
    memset(Coeff,0,sizeof(_coeff)*KEEPNUM);
    for (int i=0; i<KEEPNUM; i++) Coeff[i].index=i;
    psumanege_=false;
    psum=NULL;
  }
  ~HaarCoeffCubemap4TripleSparseStatic()
  {
    if (psumanege_)
      delete[] psum;
  }
  inline void operator*=(const VALUE_TYPE &x)
  {
    for (int i=0; i<KEEPNUM; i++)
      Coeff[i].value*=x;
    for (int i=0; i<6; i++)
      Scale[i]*=x;
  }
  inline void operator/=(const VALUE_TYPE &x)
  {
    for (int i=0; i<KEEPNUM; i++)
      Coeff[i].value/=x;
    for (int i=0; i<6; i++)
      Scale[i]/=x;
  }

  struct _sortnode{VALUE_TYPE sum;INDEX_TYPE index;int pos;};
  struct _SumGreater{bool operator()(const _sortnode &x,const _sortnode &y){return x.sum>y.sum;}};
  struct _IndexLess{bool operator()(const _sortnode &x,const _sortnode &y){return x.index<y.index;}};
  inline void operator+=(const HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,VALUE_TYPE,INDEX_TYPE> &h)
  {

    Vector<3,VALUE_TYPE> tmp[KEEPNUM*2];
    _sortnode tmp2[KEEPNUM*2];
    int cur=0,cur2=0;
    for (int cur1=0;cur1<KEEPNUM;cur1++) 
    {
      while (cur2<KEEPNUM && Coeff[cur1].index>h.Coeff[cur2].index)
      {
        tmp2[cur].index=h.Coeff[cur2].index;
        tmp2[cur].pos=cur;
        tmp[cur]=h.Coeff[cur2].value;
        tmp2[cur].sum=tmp[cur].AbsMax();
        cur++;cur2++;
      }
      if (cur2<KEEPNUM && Coeff[cur1].index==h.Coeff[cur2].index)
      {
        tmp2[cur].index=Coeff[cur1].index;
        tmp2[cur].pos=cur;
        tmp[cur]=h.Coeff[cur2].value+Coeff[cur1].value;
        tmp2[cur].sum=tmp[cur].AbsMax();
        cur++;cur2++;
        continue;
      }
      if ((cur2>=KEEPNUM) || (cur2<KEEPNUM && Coeff[cur1].index<h.Coeff[cur2].index))
      {
        tmp2[cur].index=Coeff[cur1].index;
        tmp2[cur].pos=cur;
        tmp[cur]=Coeff[cur1].value;
        tmp2[cur].sum=tmp[cur].AbsMax();
        cur++;
        continue;
      }
    }
    while (cur2<KEEPNUM)
    {
      tmp2[cur].index=h.Coeff[cur2].index;
      tmp2[cur].pos=cur;
      tmp[cur]=h.Coeff[cur2].value;
      tmp2[cur].sum=tmp[cur].AbsMax();
      cur++;cur2++;
    }
    nth_element(tmp2,tmp2+KEEPNUM,tmp2+cur,_SumGreater());
    sort(tmp2,tmp2+KEEPNUM,_IndexLess());
    for (int i=0; i<KEEPNUM; i++)
    {
      Coeff[i].value=tmp[tmp2[i].pos];
      Coeff[i].index=tmp2[i].index;
    }
    for(int i=0; i<6; i++)
      Scale[i]+=h.Scale[i];
  }
  inline const HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,VALUE_TYPE,INDEX_TYPE>& operator=(const HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,VALUE_TYPE,INDEX_TYPE> &h)
  {
    Zero();
    memcpy(Scale,h.Scale,sizeof(VALUE_TYPE)*6);
    memcpy(Coeff,h.Coeff,sizeof(_coeff)*KEEPNUM);
    return *this;
  }

  inline const HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,VALUE_TYPE,INDEX_TYPE>& operator=(const HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &h)
  {
    Zero();
    memcpy(Scale,h.Scale,sizeof(VALUE_TYPE)*6);
    if (h.Size==KEEPNUM)
      memcpy(Coeff,h.Coeff,sizeof(_coeff)*KEEPNUM);
    else if (h.Size>KEEPNUM)
    {
      _sortnode *tmp2=new _sortnode[h.Size];
      for (int i=0; i<h.Size; i++)
      {
        tmp2[i].index=h.Coeff[i].index;
        tmp2[i].pos=i;
        tmp2[i].sum=h.Coeff[i].value.AbsMax();
      }
      nth_element(tmp2,tmp2+KEEPNUM,tmp2+h.Size,_SumGreater());
      sort(tmp2,tmp2+KEEPNUM,_IndexLess());
      for (int i=0; i<KEEPNUM; i++)
      {
        Coeff[i].value=h.Coeff[tmp2[i].pos].value;
        Coeff[i].value=tmp2[i].index;
      }
    }
    else
    {
      memcpy(Coeff,h.Coeff,sizeof(_coeff)*h.Size);
      for (int cur=Coeff[h.Size-1].index,i=h.Size; i<KEEPNUM; i++)
        Coeff[i].index=cur++;
    }
    return *this;
  }

  const Vector<3,VALUE_TYPE> & operator[](INDEX_TYPE n) const
  {
    _coeff c;
    c.index=n;
    const _coeff *pos=lower_bound(Coeff,Coeff+KEEPNUM,c);
    if (pos->index==n) return pos->value;
    else return zerovalue;
  }

  _coeff *Find(INDEX_TYPE n)
  {
    _coeff c;
    c.index=n;
    _coeff *pos=lower_bound(Coeff,Coeff+KEEPNUM,c);
    if (pos->index==n) return pos;
    else return NULL;
  }
  inline void Zero()
  {
    memset(Scale,0,sizeof(VALUE_TYPE)*6);
    memset(Coeff,0,sizeof(_coeff)*KEEPNUM);
    for (int i=0; i<KEEPNUM; i++) Coeff[i].index=i;
    if (psum!=NULL)
      memset(psum,1,sizeof(VALUE_TYPE)*DATASIZE);
  }
  inline void ResetPsum()
  {
    if (psum!=NULL)
      memset(psum,1,sizeof(VALUE_TYPE)*DATASIZE);
  }
  template <int KEEPNUM2>
  VALUE_TYPE Dot(const HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM2,T1,T2> &c)const
  {
    VALUE_TYPE ret=Scale[0]*c.Scale[0]+Scale[1]*c.Scale[1]+Scale[2]*c.Scale[2]+Scale[3]*c.Scale[3]+Scale[4]*c.Scale[4]+Scale[5]*c.Scale[5];
    if (c.Size==0) return ret;
    int cur2=0;
    for (int cur1=0;cur1<KEEPNUM;cur1++)
    {
      while(cur2<KEEPNUM2 && Coeff[cur1].index>c.Coeff[cur2].index) cur2++;
      if (cur2==KEEPNUM2) break;
      if (Coeff[cur1].index==c.Coeff[cur2].index)
        ret+=Coeff[cur1].value.Dot(c.Coeff[cur2].value);
    }
    return ret;
  }
  VALUE_TYPE Dot(const HaarCoeffCubemap4TripleFull<CUBEFACEN,T1,T2> &c)const
  {
    VALUE_TYPE ret=Scale[0]*c.Scale[0]+Scale[1]*c.Scale[1]+Scale[2]*c.Scale[2]+Scale[3]*c.Scale[3]+Scale[4]*c.Scale[4]+Scale[5]*c.Scale[5];
    for (int cur1=0;cur1<KEEPNUM;cur1++)
    {
      ret+=Coeff[cur1].value.Dot(c.Square[Coeff[cur1].index]);
    }
    return ret;
  }
  void SaveToCubemap(Cubemap<VALUE_TYPE> &c)
  {
    const HaarCoeffCubemap4TripleFull<CUBEFACEN,INDEX_TYPE,INDEX_TYPE> &indextable=HaarCoeffCubemap4TripleFull<CUBEFACEN>::GetCubemapIndexTable();
    c.Zero();
    c.ChangeSize(CUBEFACEN);
    for(int sideIdx = 0; sideIdx < 6; ++sideIdx)
    {
      c.v[indextable.Scale[sideIdx]]=Scale[sideIdx];
    }
    for (int i=0; i<KEEPNUM; i++)
    {
      c.v[indextable.Square[Coeff[i].index].v[0]]=Coeff[i].value.v[0];
      c.v[indextable.Square[Coeff[i].index].v[1]]=Coeff[i].value.v[1];
      c.v[indextable.Square[Coeff[i].index].v[2]]=Coeff[i].value.v[2];
    }
  }
  friend ostream& operator<<(ostream &o, HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,T1,T2> &me)
  {
    me.SaveToFileA(o);
    return o;
  }
  friend istream& operator>>(istream &i, HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,T1,T2> &me)
  {
    me.LoadFromFileA(i);
    return i;
  }
  void SaveToFileA(ostream &fo)
  {
    fo<<Scale[0]<<' '<<Scale[1]<<' '<<Scale[2]<<' '<<Scale[3]<<' '<<Scale[4]<<' '<<Scale[5]<<endl;
    fo<<Size<<endl;
    for(int i=0; i<KEEPNUM; i++)
    {
      fo<<Coeff[i].value<<' ';
      fo<<Coeff[i].index<<' ';
    }
    fo<<endl;
  }
  void LoadFromFileA(istream &fi)
  {
    Clear();
    fi>>Scale[0]>>Scale[1]>>Scale[2]>>Scale[3]>>Scale[4]>>Scale[5];
    int size;
    fi>>size;
    if (size!=KEEPNUM)
    {
      printf("HaarCoeffCubemap4TripleSparseStatic LoadFromFileA ERROR!\n");
      return;
    }
    Coeff=new _coeff[Size];
    for(int i=0; i<KEEPNUM; i++)
    {
      fi>>Coeff[i].value;
      fi>>Coeff[i].index;
    }
  }
  void LoadFromFileA(FILE *fp)
  {
    printf("LoadFromFileA(FILE *fp) must be specilized to use!\n");
  }
  void SaveToFileB(FILE *fp)
  {
    fwrite(Scale,sizeof(VALUE_TYPE),6,fp);
    fwrite(&Size,sizeof(Size),1,fp);
    fwrite(Coeff,sizeof(_coeff),KEEPNUM,fp);
  }
  void LoadFromFileB(FILE *fp)
  {
    Clear();
    fread(Scale,sizeof(VALUE_TYPE),6,fp);
    fread(&Size,sizeof(Size),1,fp);
    if (size!=KEEPNUM)
    {
      printf("HaarCoeffCubemap4TripleSparseStatic LoadFromFileA ERROR!\n");
      return;
    }
    fread(Coeff,sizeof(_coeff),KEEPNUM,fp);
  }
};
//////////////////////////////////////////////////////////////////////////
template < int CUBEFACEN,class T1,typename T2 >
class HaarCoeffCubemap4TripleFull
{
public:
  typedef T1 VALUE_TYPE;
  typedef T2 INDEX_TYPE;
  const int LEVELN;
  static const int FACEDATASIZE=(CUBEFACEN*CUBEFACEN-1)/3;
  static const int DATASIZE=FACEDATASIZE*6;
  T1 EMPTYPSUM;
  VALUE_TYPE Scale[6];
  Vector<3,VALUE_TYPE>  Square[DATASIZE];
  T1 psum[DATASIZE];
  HaarCoeffCubemap4TripleFull()
    :LEVELN(Log2(CUBEFACEN))
  {
    memset(&EMPTYPSUM,1,sizeof(EMPTYPSUM));
//    Zero();
  }
  inline Vector<3,VALUE_TYPE> & operator[](INDEX_TYPE n)
  {
    return Square[n];
  }
  inline const Vector<3,VALUE_TYPE> & operator[](INDEX_TYPE n) const
  {
    return Square[n];
  }
  inline void Zero()
  {
    memset(Square,0,sizeof(Vector<3,VALUE_TYPE>)*DATASIZE);
    memset(psum,1,sizeof(T1)*DATASIZE);
    memset(Scale,0,sizeof(VALUE_TYPE)*6);
  }
  inline void ResetPsum()
  {
    memset(psum,1,sizeof(T1)*DATASIZE);
  }
  inline void operator=(const HaarCoeffCubemap4TripleFull<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &f)
  {
    memcpy(Scale,f.Scale,sizeof(VALUE_TYPE)*6);
    memcpy(Square,f.Square,sizeof(Vector<3,VALUE_TYPE>)*DATASIZE);
  }
  inline void operator+=(const HaarCoeffCubemap4TripleFull<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &f)
  {
    for (int i=0; i<6; i++)
      Scale[i]+=f.Scale[i];
    for (int i=0; i<DATASIZE; i++)
      Square[i]+=f.Square[i];
  }
  INDEX_TYPE SToPos(_s s,_m m,int face)
  {
    switch (m)
    {
    case M01:
      return face*CUBEFACEN*CUBEFACEN+CUBEFACEN*s.j+(1<<s.l)+s.i;
    case M10:
      return face*CUBEFACEN*CUBEFACEN+CUBEFACEN*((1<<s.l)+s.j)+s.i;
    case M11:
      return face*CUBEFACEN*CUBEFACEN+CUBEFACEN*((1<<s.l)+s.j)+(1<<s.l)+s.i;
    }
    return 0;
  }
  void LoadFromCubemap(const Cubemap<VALUE_TYPE> &c)
  {
    Vector<3,VALUE_TYPE> *pSquare = Square;
    VALUE_TYPE* pScale = Scale;
    VALUE_TYPE* Coef=c.v;
    for(int sideIdx = 0; sideIdx < 6; ++sideIdx)
    {
      *pScale++ = *(Coef + sideIdx * CUBEFACEN * CUBEFACEN);
      for(int level = 0; level < LEVELN; ++level)
        for(int iIdx = 0; iIdx < (1<<level); ++iIdx)
          for(int jIdx = 0; jIdx < (1<<level); ++jIdx)
          {
            //res * row + col
            //M01. col: 2^l +i, row: j
            pSquare->v[0] = *(Coef + sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * jIdx + (1<<level) + iIdx);
            //M10. col: i, row: 2^l+j
            pSquare->v[1] = *(Coef + sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * ((1<<level) + jIdx) + iIdx);  
            //M11. col: 2^l+i, row: 2^l+j
            pSquare->v[2] = *(Coef + sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * ((1<<level) + jIdx) + (1<<level) + iIdx);
            ++pSquare;
          }
    }
    memset(psum,1,sizeof(T1)*DATASIZE);

  }

  void SaveToCubemap(Cubemap<VALUE_TYPE> &c)
  {
    Vector<3,VALUE_TYPE> *pSquare = Square;
    VALUE_TYPE* pScale = Scale;
    VALUE_TYPE* Coef=c.v;
    for(int sideIdx = 0; sideIdx < 6; ++sideIdx)
    {
      *(Coef + sideIdx * CUBEFACEN * CUBEFACEN) = *pScale++ ;
      for(int level = 0; level < LEVELN; ++level)
        for(int iIdx = 0; iIdx < (1<<level); ++iIdx)
          for(int jIdx = 0; jIdx < (1<<level); ++jIdx)
          {
            //res * row + col
            //M01. col: 2^l +i, row: j
            *(Coef + sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * jIdx + (1<<level) + iIdx) = pSquare->x;
            //M10. col: i, row: 2^l+j
            *(Coef + sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * ((1<<level) + jIdx) + iIdx) = pSquare->y;  
            //M11. col: 2^l+i, row: 2^l+j
            *(Coef + sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * ((1<<level) + jIdx) + (1<<level) + iIdx) = pSquare->z;
            ++pSquare;
          }
    }
  }

  static const HaarCoeffCubemap4TripleFull<CUBEFACEN,INDEX_TYPE,INDEX_TYPE> &GetCubemapIndexTable()
  {
    static bool init=false;
    static HaarCoeffCubemap4TripleFull<CUBEFACEN,INDEX_TYPE,INDEX_TYPE> indextable;
    if (init==false)
    {
      Vector<3,INDEX_TYPE> *pSquare = indextable.Square;
      INDEX_TYPE* pScale = indextable.Scale;
      for(int sideIdx = 0; sideIdx < 6; ++sideIdx)
      {
        *pScale++ = sideIdx * CUBEFACEN * CUBEFACEN;
        for(int level = 0; level < indextable.LEVELN; ++level) for(int iIdx = 0; iIdx < (1<<level); ++iIdx) for(int jIdx = 0; jIdx < (1<<level); ++jIdx)
        {
          pSquare->v[0] = sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * jIdx + (1<<level) + iIdx;
          pSquare->v[1] = sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * ((1<<level) + jIdx) + iIdx;  
          pSquare->v[2] = sideIdx*CUBEFACEN*CUBEFACEN + CUBEFACEN * ((1<<level) + jIdx) + (1<<level) + iIdx;
          ++pSquare;
        }
      }
      init=true;
    }
    return indextable;
  }

  struct _sortnode{VALUE_TYPE first;INDEX_TYPE second;};
  struct _Greater{bool operator()(const _sortnode &a,const _sortnode &b){return a.first>b.first;};};
  struct _idxLess{bool operator()(const _sortnode &a,const _sortnode &b){return a.second<b.second;};};
  void KeepBigElement(int keepNum, HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &BigElement, bool bAreaWeighted=false)
  {
    const int sideNum = FACEDATASIZE;
    _sortnode CoefFabAndIdx[FACEDATASIZE*6];
    if(bAreaWeighted)
    {
      for(int i = 0; i < sideNum*6; ++i)  
      {
        Vector<3,VALUE_TYPE> weightedCoef = Square[i] / float(1 << Log2((i % sideNum) / CUBEFACEN));
        CoefFabAndIdx[i].first = weightedCoef.AbsMax();
        CoefFabAndIdx[i].second = i;
      }
    }
    else
    {
      for(short int i = 0; i < (short int)sideNum*6; ++i)  
      {
        CoefFabAndIdx[i].first = Square[i].AbsMax();
        CoefFabAndIdx[i].second = i;
      }
    }
    //now CoefFabAndIdx are all >0
    nth_element(CoefFabAndIdx, CoefFabAndIdx + keepNum, CoefFabAndIdx+FACEDATASIZE*6, _Greater());
#ifdef SPARSENEW
#else
    sort(CoefFabAndIdx, CoefFabAndIdx + keepNum, _idxLess());
#endif
    //bigCoefs and corresponding indices in the same position in coefIndices
    BigElement.Create(keepNum);
    for (int i = 0; i < keepNum; ++i)
    {
      BigElement.Coeff[i].value = Square[CoefFabAndIdx[i].second];
      BigElement.Coeff[i].index = CoefFabAndIdx[i].second;
    }
    memcpy(BigElement.Scale,Scale,sizeof(VALUE_TYPE)*6);
    BigElement.PrepareIndexToLocal();
  }

  void KeepBigElement(float keepRatio, HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &BigElement, bool bAreaWeighted=false)
  {
    const int sideNum = FACEDATASIZE;
    _sortnode CoefFabAndIdx[FACEDATASIZE*6];
    VALUE_TYPE ori_energe=0,keep_energe,scale_energe=0;
    for (int i=0; i<6; i++)
      scale_energe+=Scale[i]*Scale[i];
    ori_energe=scale_energe;
    if(bAreaWeighted)
    {
      for(INDEX_TYPE i = 0; i < sideNum*6; ++i)  
      {
        Vector<3,VALUE_TYPE> weightedCoef = Square[i] / float(1 << Log2((i % sideNum) / CUBEFACEN));
        CoefFabAndIdx[i].first = weightedCoef.AbsMax();
        CoefFabAndIdx[i].second = i;
        ori_energe+=CoefFabAndIdx[i].first*CoefFabAndIdx[i].first;
      }
    }
    else
    {
      for(INDEX_TYPE i = 0; i < sideNum*6; ++i)  
      {
        CoefFabAndIdx[i].first = Square[i].AbsMax();
        CoefFabAndIdx[i].second = i;
        ori_energe+=CoefFabAndIdx[i].first*CoefFabAndIdx[i].first;
      }
    }
    keep_energe=ori_energe*keepRatio;
    sort(CoefFabAndIdx, CoefFabAndIdx+FACEDATASIZE*6, _Greater());
    VALUE_TYPE got_energe=scale_energe;
    int keepNum=0;
    for(INDEX_TYPE i = 0; i < sideNum*6; ++i)  
    {
      got_energe+=CoefFabAndIdx[i].first*CoefFabAndIdx[i].first;
      if (got_energe>=keep_energe)
      {
        keepNum=i+1;
        break;
      }
    }
#ifdef SPARSENEW
#else
    sort(CoefFabAndIdx, CoefFabAndIdx + keepNum, _idxLess());
#endif
    //bigCoefs and corresponding indices in the same position in coefIndices
    BigElement.Create(keepNum);
    for (int i = 0; i < keepNum; ++i)
    {
      BigElement.Coeff[i].value = Square[CoefFabAndIdx[i].second];
      BigElement.Coeff[i].index = CoefFabAndIdx[i].second;
    }
    memcpy(BigElement.Scale,Scale,sizeof(VALUE_TYPE)*6);
    BigElement.PrepareIndexToLocal();
  }

  template <int KEEPNUM>
  void KeepBigElement(HaarCoeffCubemap4TripleSparseStatic<CUBEFACEN,KEEPNUM,VALUE_TYPE,INDEX_TYPE> &BigElement, bool bAreaWeighted=false)
  {
    const int sideNum = FACEDATASIZE;
    vector<pair<VALUE_TYPE, INDEX_TYPE> > CoefFabAndIdx(sideNum * 6);  
    if(bAreaWeighted)
    {
      for(short int i = 0; i < (short int)sideNum*6; ++i)  
      {
        Vector<3,VALUE_TYPE> weightedCoef = Square[i] / float(1 << Log2((i % sideNum) / CUBEFACEN));
        CoefFabAndIdx[i] = pair<VALUE_TYPE, INDEX_TYPE>(weightedCoef.absmax(), i);
      }
    }
    else
    {
      for(short int i = 0; i < (short int)sideNum*6; ++i)  
      {
        CoefFabAndIdx[i] = pair<VALUE_TYPE, INDEX_TYPE>(Square[i].absmax(), i);
      }
    }
    //now CoefFabAndIdx are all >0
    nth_element(CoefFabAndIdx.begin(), CoefFabAndIdx.begin() + KEEPNUM, CoefFabAndIdx.end(), _Greater()); //cut off: first keepNum element is biggest
    sort(CoefFabAndIdx.begin(), CoefFabAndIdx.begin() + KEEPNUM, _idxLess()); //for real-time 3p indexing, sort into s/l/i/j/m increasing order. Refer to Ng04

    //bigCoefs and corresponding indices in the same position in coefIndices
    for (int i = 0; i < KEEPNUM; ++i)
    {
      BigElement.Coeff[i].value = Square[CoefFabAndIdx[i].second];
      BigElement.Coeff[i].index = CoefFabAndIdx[i].second;
    }
    for (int i=0; i<6; i++)
      BigElement.Scale[i]=Scale[i];
  }

  void LoadFromSparse(HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &BigElement)
  {
    Zero();
    for (int i=0; i<6; i++)
      Scale[i]=BigElement.Scale[i];
    for (int i=0; i<BigElement.Size; i++)
    {
#ifdef SPARSENEW
      if (BigElement.Coeff[i].value.v[0]==EMPTYPSUM) continue;
#endif
      Square[BigElement.Coeff[i].index]=BigElement.Coeff[i].value;
    }
  }

  VALUE_TYPE Dot(const HaarCoeffCubemap4TripleFull<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &c) const
  {
    VALUE_TYPE ret=Scale[0]*c.Scale[0]+Scale[1]*c.Scale[1]+Scale[2]*c.Scale[2]+Scale[3]*c.Scale[3]+Scale[4]*c.Scale[4]+Scale[5]*c.Scale[5];
    for (int i=0; i<DATASIZE; i++)
      ret+=Square[i].Dot(c.Square[i]);
    return ret;
  }

  VALUE_TYPE Dot(const HaarCoeffCubemap4TripleSparse<CUBEFACEN,VALUE_TYPE,INDEX_TYPE> &c) const
  {
    VALUE_TYPE ret=Scale[0]*c.Scale[0]+Scale[1]*c.Scale[1]+Scale[2]*c.Scale[2]+Scale[3]*c.Scale[3]+Scale[4]*c.Scale[4]+Scale[5]*c.Scale[5];
    for (int i=0; i<c.Size; i++)
      ret+=Square[c.Coeff[i].index].Dot(c.Coeff[i].value);
    return ret;
  }
};

}